package org.example.myleet.p1482;

/**
 * 27 ms
 * 二分法
 */
public class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if (bloomDay.length < m) {
            return -1;
        }
        int l = Integer.MAX_VALUE, r = 0;
        for (int d : bloomDay) {
            r = Math.max(r, d);
            l = Math.min(l, d);
        }
        //二分法确定答案所在
        int mid;
        while (r - l > 1) {
            mid = (r + l) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (canMake(bloomDay, m, k, l)) {
            return l;
        }
        if (canMake(bloomDay, m, k, r)) {
            return r;
        }
        //找不到答案
        return -1;
    }

    /**
     * 判断在d天的情况下能否完成花束制作任务
     */
    private boolean canMake(int[] bloomDay, int m, int k, int d) {
        int dayLen = bloomDay.length;
        int bunch = 0, flowers = 0;
        for (int i = 0; i < dayLen; ++i) {
            if (bloomDay[i] <= d) {
                //如果有花开了，那么采花+1
                ++flowers;
                if (flowers >= k) {
                    //攒够了一束花
                    flowers = 0;
                    ++bunch;
                    if (bunch >= m) {
                        //如果花束够了，说明找到答案了
                        return true;
                    }
                }
            } else {
                //中间缺了一朵花，重新采花
                flowers = 0;
            }
        }
        return false;
    }
}
